def subtract(ver_a, ver_b):
    return ver_a.subtract(ver_b)

def vs_subtract(vs_a, vs_b):
    return VerSetSubtractionIter(vs_a, vs_b)

class SetIter:
    def __init__(self, s):
	self.s_ = s
	self.cur_ = 0

    def __iter__(self):
	return self

    def next_with_pos(self):
	while True:
	    if self.cur_ > self.s_.max_ver_:
		raise StopIteration()
	    d = self.s_.get(self.cur_)
	    self.cur_ = self.cur_ + 1
	    if d != None:
		return d, self.cur_ - 1

    def next(self):
	return self.next_with_pos()[0]

class SetSubtractionIter:
    def __init__(self, s1, s2):
	self.s1_  = s1
	self.s2_  = s2
	self.max_ = max(s1.max_ver_, s2.max_ver_)
	self.cur_ = 0

    def __iter__(self):
	return self

    def __str__(self):
	return '<SetSubtractionIter max = %d, cur = %d' % (self.max_,
		self.cur_)

    def next_with_pos(self):
	while True:
	    if self.cur_ > self.max_:
		raise StopIteration()
	    a = self.s1_.get(self.cur_)
	    b = self.s2_.get(self.cur_)
	    self.cur_ = self.cur_ + 1
	    if a != None and b is None:
		return a, self.cur_ - 1

    def next(self):
	return self.next_with_pos()[0]

class VerSetSubtractionIter:
    """Will iterate through {id:Set(), id:Set(), ...} in a round robin
    manner."""
    def __init__(self, vs1, vs2):
        assert isinstance(vs1, VerSet)
        assert isinstance(vs2, VerSet)
        
	self.vs1_ = vs1
	self.vs2_ = vs2
	self.rotate_ = 0

	self.fringe_ = {}
	for k in self.vs1_.keys():
	    self.fringe_[k] = SetSubtractionIter(self.vs1_[k], self.vs2_[k])

    def __iter__(self):
	return self

    def __str__(self):
	return str(self.fringe_)

    def rotated_ids(self):
	k = self.fringe_.keys()
        if len(k) == 0:
            return []
	i = self.rotate_ % len(k)
	r = k[i:] 
	r.extend(k[:i])
	self.rotate_ = self.rotate_ + 1
	return r

    def next_with_pos(self):
	for k in self.rotated_ids():
	    try:
		elt, pos = self.fringe_[k].next_with_pos()
		return elt, k, pos
	    except StopIteration:
		pass
	raise StopIteration()

    def next(self):
	return self.next_with_pos()[0]

class Set:
    """Efficiently and durably stores a set of versions.
    XXX/bowei -- does neither right now"""
    def __init__(self):
	self.sets_ = {}
	self.max_ver_ = -1

    def __iter__(self):
	return SetIter(self)

    def __str__(self):
	return str(self.sets_)

    def set(self, version, data):
	self.sets_[version] = data
	if version > self.max_ver_:
	    self.max_ver_ = version

    def get(self, version):
	return self.sets_.get(version)

    def subtract(self, verset):
	"""Returns an iterable sequence SetItr."""
	return SetSubtractionIter(self, verset)

    def get_compact_encoding(self):
        symbol = self.get(0)
        cur_symbol = self.get(0)
        count = 1
        output = []
        v = 1
	for v in xrange(1, self.max_ver_ + 1):
            symbol = self.get(v)
            if cur_symbol != symbol:
                output.append((cur_symbol, v - count, v))
                count = 0
                cur_symbol = symbol
            count = count + 1
        if len(self.sets_) == 0:
            return []
        elif v == 1:
            output.append((symbol, v - count, v))
        elif v >= 2:
            output.append((symbol, v - count + 1, v + 1))
        return output

    def from_compact_encoding(self, encoding):
        for e in encoding:
            for i in xrange(e[1], e[2]):
                self.sets_[i] = e[0]
                self.max_ver_ = e[2] - 1


class VerSet:
    def __init__(self):
        self.versions_ = {}

    def __str__(self):
	return str(self.versions_)

    def keys(self):
        return self.versions_.keys()

    def get(self, key):
        return self.versions_.get(key)

    def __getitem__(self, key):
        s = self.versions_.get(key)
        if s is None:
	    s = Set()
	    self.versions_[key] = s
	return s

    def __setitem__(self, key, val):
        assert isinstance(val, Set)
        self.versions_[key] = val

    def __iter__(self):
        return iter(self.versions_)

    def __contains__(self, item):
        return item in self.versions_
        
if __name__ == "__main__":
    a = Set()
    a.set(0, 'a')
    a.set(2, 'b')
    a.set(3, 'b')
    a.set(4, 'c')
    a.set(7, 'c')

    b = Set()
    b.set(1, 'a')
    b.set(3, 'b')
    b.set(4, 'c')
    b.set(6, 'd')

    c = Set()
    c.set(0, 'a')

    aa = Set()
    aa.from_compact_encoding(a.get_compact_encoding())
    assert(a.get_compact_encoding() == aa.get_compact_encoding())
    bb = Set()
    bb.from_compact_encoding(b.get_compact_encoding())
    assert(b.get_compact_encoding() == bb.get_compact_encoding())
    cc = Set()
    cc.from_compact_encoding(c.get_compact_encoding())
    assert(c.get_compact_encoding() == cc.get_compact_encoding())

    vs1 = {}
    s = Set()
    s.set(0, True)
    s.set(1, True)
    s.set(2, True)
    s.set(5, True)
    s.set(6, True)
    s.set(7, True)
    vs1['a'] = s

    s = Set()
    s.set(0, True)
    s.set(1, True)
    s.set(2, True)
    s.set(9, True)
    s.set(5, True)
    vs1['b'] = s

    s = Set()
    s.set(0, True)
    s.set(5, True)
    s.set(2, True)
    vs1['c'] = s

    vs2 = {}
    s = Set()
    s.set(0, True)
    s.set(2, True)
    s.set(5, True)
    s.set(6, True)
    s.set(9, True)
    s.set(3, True)
    s.set(16, True)
    vs2['a'] = s

    s = Set()
    s.set(0, True)
    s.set(1, True)
    s.set(5, True)
    s.set(7, True)
    vs2['b'] = s

    s = Set()
    s.set(5, True)
    vs2['c'] = s

    i = vs_subtract(vs1, vs2)
    l = []
    try:
	while True:
	    l.append(i.next_with_pos())
    except StopIteration:
	pass
    print l
